"""
https://leetcode.cn/problems/longest-valid-parentheses/description/

32. 最长有效括号
困难
相关标签
相关企业
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
子串
的长度。

 

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0
 

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
"""

from typing import List


class Solution:
    """
    某个字符串有效的标记是：
    从最左侧开始遍历，同时维护一个标记数，初始值为0，
    出现(则记为+1,出现)则-1,
    整个过程如果没有任何时候标记数均不小于0，且最后标记数为0，
    则这个字符串就是有效的

    如果一个子字符串，如从0到1构建为一个有效字符串，则有效长度为end-start+1

    仍按照：https://algo.itcharge.cn/Solutions/0001-0099/longest-valid-parentheses/#%E6%80%9D%E8%B7%AF-2-%E6%A0%88
    的栈思路来

    """
    def longestValidParentheses(self, s: str) -> int:
        stack=[-1]
        ans=0
        for i,ch in enumerate(s):
            if ch=='(':
                stack.append(i)
            else:
                # 由于哨兵节点的存在，总是可以进行pop
                stack.pop()
                if stack:
                    # 注：由于之前已经进行了pop操作，此处的stack[-1]记录的不是)对应的(的位置，而是这之前。可能为(的位置-1。
                    # 如果将()视为一层层嵌套的关系，则stack[-1]记录的则是当前层级()的最早计算位置
                    # 也因此，需要一个哨兵标记为第一层级的开始计算位置。使用栈进行计算的时候，涉及层级的概念时，均可考虑增加这么一个哨兵，来表示层级的开始计算位置
                    # 在此例中，尽管有层级的概念，但最后不一定能构建完整的层级。但这不影响利用层级栈
                    ans=max(ans,i-stack[-1])
                else:
                    # 维护哨兵节点，该哨兵节点仅位置有意义，作为下一次层级（如果有）的起始计算位置
                    stack.append(i)
        return ans

if __name__=='__main__':
    sol=Solution()
    params=[
        ('()',2),
        ('(()',2),
        (')()())',4),
        ('()(()',2),
        ('(()()',4),
        ('))))((()((',2),
        ('(())',2)
    ]
    for s,ast in params:
        res=sol.longestValidParentheses(s)
        print(res,res==ast)


    pass